\documentclass[UTF8]{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{ctex}
\setlength{\parindent}{2em}

\title{Homework 6:数据结构间的关系}

\author{唐瑞良\\ 强基工程力学 3210105852}

\begin{document}

\maketitle
\section{链表和树}
\subsection{派生关系}
\indent 这两种数据结构的最基本的特征是单个节点。对于链表，从节点类可直接派生出两个$Node$类。对于树，存在以下的派生关系：$Node->BinaryNode->BinaryTree->BinarySearchTree->AvlTree$\\
\subsection{派生信息}
\indent 对于基本的$Node$，其应当具有存储值，存储指针，初始化节点，获取值的功能。通过单个$Node$的结构体和公有函数$get_value()$实现。\\
\indent 对于链表，需要在$Node$的基础上增加插入，删除，查找，遍历的功能，同时$Node$类中的指针被用来连接节点。这些功能通过公有函数$insert(),delete(),iterator\_find(),read\_all()$实现。\\
\indent 对于$BinaryNode$,基于$Node$的基础上将指针定义为了左右节点。需要派生出根节点$root$.\\
\indent 对于$BinaryTree$,基于$BinaryNode$需要增加插入，删除，寻找最大最小值，查找值，打印树，清空树的功能，前面几个功能和链表是类似的。通过引入函数$insert(),delete\_node(),findMin(),findMax(),printTree(),makeEmpty()$实现。\\
\indent 对于$BinarySearchTree$,需要根据排序需要提供插入数组元素的接口。\\
\indent 对于$AvlTree$,为了实现对树的平衡，需要加入旋转左右子树的操作，通过$rotateXXXX()$类型的函数实现。同时$AvlNode$需要从$Node$类派生并加入$height$信息。\\

\section{哈希}
\indent 哈希能够实现插入，删除，寻找等功能。与树相比，虽然它不能实现寻找最大最小值等功能，但他能够在常数时间内实现前述功能。\\
\indent 哈希的基本思想是通过散列函数，对确定的关键字通过该函数能够得到其在哈希表中的位置。他具有性质：位置不同的关键字一定不相同，相同位置的关键字通常是相同的，但有时会出现哈希碰撞。为了避免哈希碰撞，我们总希望散列函数是均匀的，即对不同的关键字，各个位置都能够等可能的取到。一般采用取质数的余的方法，除此之外还有平方取中等方法。对于关键字，应当在合理的基础上以合适的方法取少量字符做运算，避免由于字符过长导致计算哈希值的过大时间开销。\\
\indent 通常也会采用改变哈希表构造的方法规避哈希碰撞的问题，比如让每个$cell$都作为一条链表。对于不用链表的方法，我们有开放寻址法，平方探测法，双重散列法。是当存储位置发生冲突时，为后存储的数据寻找其他的未占用的位置的方法。\\
\indent 另外当一个哈希表存储的数据占比过多时，会降低使用哈希的效率，这时可以采用重哈希的方法将其塞到更大的哈希表中。
\end{document}
